package com.lw.leetcode.stack.c;

import java.util.Arrays;
import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * 1840. 最高建筑高度
 *
 * @author liw
 * @version 1.0
 * @date 2022/4/24 13:32
 */
public class MaxBuilding {


    public static void main(String[] args) {
        MaxBuilding test = new MaxBuilding();

        // 2
//        int n = 5;
//        int[][] restrictions = {{2, 1}, {4, 1}};

        // 5
//        int n = 6;
//        int[][] restrictions = {};

        // 5
        int n = 10;
        int[][] restrictions = {{5,3},{2,5},{7,4},{10,3}};

        int i = test.maxBuilding(n, restrictions);
        System.out.println(i);
    }

    public int maxBuilding(int n, int[][] restrictions) {
        if (restrictions.length == 0) {
            return n - 1;
        }
        Arrays.sort(restrictions, (a, b) -> Integer.compare(a[0], b[0]));
        Stack<Integer> indexs = new Stack<>();
        Stack<Integer> hights = new Stack<>();
        indexs.add(1);
        hights.add(0);
        for (int[] arr : restrictions) {
            int c = arr[0];
            int h = arr[1];
            int lc = indexs.peek();
            int lh = hights.peek();
            if (c - lc + lh < h) {
                continue;
            }
            while (c - lc + h < lh) {
                indexs.pop();
                hights.pop();
                lc = indexs.peek();
                lh = hights.peek();
            }
            indexs.add(c);
            hights.add(h);
        }
//        System.out.println(indexs);
//        System.out.println(hights);
        int c = n;
        int h = n - indexs.peek() + hights.peek();
        int max = 0;
        while (!indexs.isEmpty()) {
            int lc = indexs.pop();
            int lh = hights.pop();
            max = Math.max(max, lh + ((h + c - lc - lh) >> 1));
            c = lc;
            h = lh;
        }
        return max;
    }

}
